Residue arithmetic is one of the fastest numerical computing methods available due to its parallel arithmetic computational properties. Computation methods using residue arithmetic are particularly suited for implementation using optical processors arranged to operate on data using pipelining techniques. Optical numerical computers possess several advantages over electronic computers, including the inherent parallelism of optical systems, the possibility of wave length multiplexing, and the short propagation time of optical signals.
The residue number system is extremely well matched to optical computing systems due to the fact that no carry mechanism is needed in residue arithmetic. This allows all the computations to be performed in parallel, without the need for interconnection between the results of sub-calculations until the final decoding step, which returns the calculation results to a more conventional number system. Also, the residue number system decomposes a calculation into sub-calculations of smaller computational complexity. Once a calculation requiring a large dynamic range is decomposed into segments that can be handled directly by conventional analog methods, the full advantage of parallel processing using optical computer systems can be utilized to handle these segments.
Optical processors using special maps to perform residue arithmetic implemented by optical processors is known per se in the art. See, for example, "Optical Computation Using Residue Arithmetic", by HUANG, et al, Applied Optics, Vol. 18, No. 2, Jan. 15, 1979. As mentioned previously, the main characteristic of the residue number system is that there are no carries, thus all of the columns of a calculation can be processed in parallel. The residue number system is based upon N fixed, prime integers m.sub.1, m.sub.2, . . . , m.sub.N, which are called moduli. For example, for a residue number system based on moduli 2, 3, 5 and 7, an integer number X=14 can be represented as 14=(R.sub.1, R.sub.2, R.sub.3, R.sub.4)=(0, 2, 4, 0), that is, a number represented by the series of integers which constitute the remainders, or residues when that number is divided by each of the chosen moduli of the residue number system.
In the performance of basic arithmetic operations, computations with respect to each of the residues may be carried out independently because of the absence of carry as noted above. For example, in the addition of two numbers in the residue number system, the two residues of each modulus are added and the residue representation of the sum of the two numbers will simply be the ensemble of the sums of the individual residues. That is, if (A.sub.1, A.sub.2, . . . , A.sub.N) and (B.sub.1, B.sub.2, . . . , B.sub.N) are the residue representations of A and B, respectively, then A+B=(A.sub.1 +B.sub.1), (A.sub.2 +B.sub.2), . . . , (A.sub.N +B.sub.N). Subtraction and multiplication operations are equally simple, while division is more difficult in the residue number system and generally involves several steps. Effort is usually made to structure algorithms so as to avoid the necessity for division.
Because the residues which collectively constitute a numerical representation in the residue number system may be processed separately to generate partial functions which collectively constitute the numerical representation of an arithmetic function of two input numerical representations, an arithmetic processor for residue numbers may be constructed from a plurality of modules, each of which operates on a single residue in the numerical representation of a number being arithmetically processed. Since the non-divisional processing of each residue only requires a single step, and no carries are involved, the entire arithmetic operation can be performed in a single step, with the output of each of the processor modules providing one residue representation of the output of the processor.
In residue arithmetic, the functions of varying numbers are cyclical. That is, the residue for a single modulus ranges between zero and one less than that modulus. This feature allows the use of maps to generate the functions of a given arithmetic operation of a variable residue. The input to the map is a signal representative of a variable residue and the output signal is a representation of the function of the input and the given operation. For example, the truth table for A+4=C modulo 5 is:
______________________________________ A C ______________________________________ 0 4 1 0 2 1 3 2 4 3 ______________________________________
This can be implemented in the two dimensional map shown in FIG. 1a. Electronic computers based on hardware or software maps of this type have required a look-up table or some form of external logic for the selection of the appropriate map. After the map is selected for the desired function, the map is then implemented optically, electro-optically or electronically.
The use of look-up tables or additional decision logic for the selection of the appropriate map substantially adds to total computational time. Optical implementation of the mapping concept mentioned above has the benefit of increasing computational speed, however, those prior art optical systems proposed for implementing the mapping technique lack flexibility and are rather complicated in their approach to selecting and programming the maps.
Accordingly, it is a primary object of the present invention to provide a multi-purpose, programmable computational module for use with a numerical optical computer which enables addition and multiplication operations to be performed in residue arithmetic in a single electronic switching step without the need for external logic or look-up tables.
A further object of the invention is to provide a computational module of the type mentioned above which can be interconnected for performing chain calculations.
Another object of the invention is to provide a computational module of the type mentioned above which reduces overall computation time and is particularly simple in construction, but yet is highly flexible to allow interconnection with other computational modules in order to allow execution of complex mathematical functions using the residue arithmetic system.
A still further object of the invention is to provide a computational module in which the input, output and program controls are all similarly represented in the form of spatial positions, thereby defining a spatial map inherent in the module for executing a particular mathematical function.
Another object of the invention is to provide a module as described above which may be easily programmed by means of electric pulses, and in which computations are carried out by the propagation of light pulses.